1. Field of Invention
This invention relates to systems and methods for processing images using filters. More specifically, this invention relates to systems and methods for designing and implementing image processing filters using templates wherein the filters operate on gray-scale images and the templates identify gray-scale image features for the purposes of modification or for extracting some image statistic, and for the purposes of optimization for the human visual system, or compatibility with other system modules, such as, compression algorithms, recognition algorithms and those occurring in printing and display devices.
2. Description of Related Art
A wide variety of digital document processing tasks are performed using template-based filters. Illustratively, digital document processing tasks include resolution conversion, enhancement, restoration, appearance tuning and de-screening of images. These tasks are commonly performed on monochrome and color images, as well as binary and continuous tone images. Although, due to the binary nature of conventional templates, implementing many digital document-processing tasks on continuous tone images has been problematic prior to the present invention. A continuous tone image may also be referred to as a gray-scale image.
In conventional systems and methods, a typical filter includes template operators to perform filtering of the images, where, a filter may be characterized as an operator or device that transforms one image into another image or transforms an image to a collection of information, such as image statistics. The filter is formed of a number of imaging template operators, often simply referred to as templates. These templates may be, for example, stored in a look-up table and implemented using a look-up table formalism. Or other equivalent formalisms, such as Boolean logic may be employed. The number of templates in a filter may vary between a small number of templates to thousands of templates. Due to its versatility in design, a look-up table is typically used to implement a template-based filter.
A raster is a one-dimensional array of image data, reflecting a single line of data across a single dimension, i.e., the length or the width, of the image. Further, each location, or xe2x80x9cpicture element,xe2x80x9d in an image may be called a xe2x80x9cpixel.xe2x80x9d In an array defining an image in which each item of data provides a value, each value indicating the properties of a location may be called a pixel value. Each pixel value is a bit in a binary form of an image, a gray-scale value in a gray-scale form of an image, or a set of color-spaced coordinates in a color coordinate form of an image. The binary form, gray-scale form, and color coordinate form are each arranged typically in a two-dimensional array, which defines an image. An N-dimensional array is typically used for an N-dimensional images, where for example, N=3 for 3-dimensional topographic images.
Using the typical binary image processing setting as an example, the filter, using the templates, transforms certain observed pixel patterns in a binary image, for example, into a corresponding enhanced binary pixel pattern. Specifically, the filter observes an arrangement of pixels using a suitable window or mask. A window is an imaging algorithmic device that observes a plurality of pixels at the same time, where the plurality of pixels is located about a target pixel. The values and locations of the observed pixels are inputted into the template matching operations. After observing the arrangement of pixels, about a target pixel, the filter then attempts to match the observed pixel pattern with one or more of the templates in the look-up table. If the look-up table contains a match to the observed pixel pattern, the look-up table generates an appropriate output. The output may be an enhanced pixel pattern for the target pixel that corresponds to the observed pixel pattern. The output could also be information in other forms; for example, the output could be a code denoting the match condition, or a data to be used for a statistical characterization of image regions.
A wide variety of types and sizes of observation windows or masks are known. The particular window used in a particular application depends on the image to be analyzed and the particular process to be performed on the image. Illustratively, a 3xc3x973 window may be used to process an image. The 3xc3x973 window, at various locations in the image, observes a 3xc3x973 block, i.e., a 9-pixel block, of binary-valued pixels, for example. One pixel in the window is the target pixel, which is typically the center pixel, while the other pixels in the window are the neighboring pixels. The target pixel and the neighboring pixels form a neighborhood. The window is typically scanned across an image advancing from target pixel to target pixel.
After the neighborhood is observed in the window, the neighborhood is then processed in some manner. For example, the observed neighborhood may be transformed into a vector. The vector is expressed in the form of (x1, x2 . . . xN) where N As the number of pixels in the neighborhood and is used to represent the properties of the target pixel, including the neighborhood of the target pixel. Each element of the vector represents one of the pixels observed in the window. The vector is then used in the look-up table to generate a desired output, for example.
A look-up table may be created in a wide variety of ways. Typically, an input value is input into the look-up table and, in response, the look-up table outputs an output value. Further, the look-up table is typically created using a training image or a set of training images. xe2x80x9cRestoration and Enhancement of Digital Documents,xe2x80x9d by R. Loce and E. Dougherty, teaches a variety of methods for designing templates based on sets of training images. The training images will occur in pairs, where one member is the xe2x80x9ctypically input image,xe2x80x9d or the xe2x80x9ctypically observed image,xe2x80x9d i.e., the xe2x80x9cobserved image,xe2x80x9d and the other image is the xe2x80x9cideal desired processed version of the image,xe2x80x9d i.e., the xe2x80x9cideal image.xe2x80x9d The training image pairs may be input into a computer program that acquires and analyzes pattern statistics between the two images, i.e., using computer-aided filter design techniques.
Conventional computer-aided filter design may be accomplished through using training-sets of document bitmaps, for example.
Illustratively, for designing a filter that enhances from a binary state to a gray-scale state, for a given pattern that occurs in the binary image about a target pixel, a training analysis system examines a target pixel at that corresponding location in the gray-scale image. The center of the window may be placed at the target pixel, for example. Based on the set of gray-scale pixels in the gray-scale image that are associated with corresponding target pixels in the binary image and gray-scale image, and associated with a similar neighborhood pixel pattern, a xe2x80x9cbest gray-scale pixel valuexe2x80x9d is determined for processing a target pixel that possess that pattern of neighborhood pixels. In other words, a template is created for the target pixels in the binary image possessing similar neighborhood pixel patterns. This analysis is performed for all binary patterns that are significant.
In this process of template selection, significance may be due to attributes such as the pixel pattern""s frequency of occurrence, the pattern""s effect on the generated image, or both. Accordingly, if a template, i.e., a pattern of pixels in the binary image, is considered significant with respect to template inclusion in the design process, that template will appear in the template-matching filter. Upon operating on an input image, if that pattern is observed, the observed target pixel value will be assigned or associated with a certain value, i.e., a corresponding gray-scale value. Both the observed neighborhood and the corresponding gray-scale value may be stored in the look-up table. Accordingly, the look-up table accepts input values and outputs a desired corresponding output value, i.e., maps input values to an ideal corresponding output value.
However, it should be apparent that this input/output process may be performed in various other ways without using a look-up table. One alternative approach that is equivalent to using a look-up table representation is a Boolean logic representation. In the Boolean logic representation, pixel values are used as variables in the logic architecture, such as a logical sum of products. The goal of template filter design using Boolean logic representation is to derive optimized Boolean operators, preferably statistically optimized Boolean operators.
As illustrated in FIG. 1 there is shown the basic process for template matching based on an observed image. Initially an observed image will occur (10) from which an ideal image is warranted (15). In order to generate an image as close as possible to the ideal image, a generated image (25) is created by utilizing a template matching operation (20). With the above understanding of the image processing setting we see that it is greatly desired to produce a generated image as similar as possible to the ideal image.
The conventional template matching operation is a binary matching process whereby a binary template or filter is to applied to a binary image.
For example, as illustrated in FIG. 2A a binary image (50) is initially sent to a data buffering circuit (55). After which, a binary pattern matching operation (60) is performed. Binary templates are typically defined as possessing ones, zeros, and xe2x80x9cdon""t cares.xe2x80x9d With reference to FIG. 2B there is shown a typical binary matching template structure. For example, the binary templates in this example are defined with ones and X""s for use in the binary matching step, where xe2x80x9cXxe2x80x9d denotes xe2x80x9cdon""t carexe2x80x9d. After combining the buffered image data and the templates in the binary pattern matching operation (60), an enhanced data buffering step (65) to create the enhanced image (70) is exercised.
Illustrated in FIGS. 4A, 4B, and 4C is the set of images associated with an image restoration application using a filter defined by templates representing particular Boolean functions applied to a received image. FIG. 3A shows a representation of a 3xc3x973 window and the positions of pixels (x1, . . . , x9). The filter defined by this window and the templates of FIG. 2B possesses the Boolean function representation shown in FIG. 3B as follows:
y=f(x1, x2, . . . , x9)=x5+x4 x6+x1 x9+x2 x8+x3 x7xe2x80x83xe2x80x83(1)
When employed as a translation-invariant filter, the singleton template x5 behaves as an identity operator: whatever pixels are valued one and zero in the input image are valued one and zero in the output image, respectively. ORed onto that identity image is the result of each 2-pixel logical product. The templates corresponding to those products possess structures that straddle the origin pixel. In this configuration a template can xe2x80x9cfitxe2x80x9d, or yield a 1, when positioned about a hole or break in a character stroke. Equation 1 is an example of an image processing operator that can be employed to repair breaks in character strokes within an image. FIG. 4 is an example of applying Equation 1 as a filter operating on an image, where FIG. 4A shows an ideal image, 4B shows an input image, and 4C shows the image resulting from applying Equation 1 as a filter to the image of FIG. 4B., The filter defined by Equation 1 produced a character (120) more likely to be recognized in character recognition operation. The restoration is not perfect. A more complicated (more and different products) filter could achieve better restoration. As shown in FIG. 4A and FIG. 4C there are still differences between the ideal image 100 and the generated image 120 resulting from the use of the filtering process defined by Equation 1.
As illustrated in FIG. 5A a system of the prior art is shown where an input image 150 is processed by a process 165 that includes binary-template-based filters 160 and combinatorial logic 170 [changed t to match the figure]; from which an output image 175 is generated and subsequently sent to a digital printer, high resolution printer or high resolution display 180.
Loose-gray-scale template matching is a windowed operation (filter) that operates on gray or partial gray images and signals. In some ways it can be thought of as an extension of the widely practiced binary template matching methods into gray-scale. Template matching operations performed on binary data (line width control, resolution enhancement, document clean up, etc.) should also be performed on partial gray imaged obtained via antialiasing or scanning. Exact matching in gray-scale would often require a prohibitively large number of templates, hence loose fitting has been developed so that a range image signals could be matched by a single template. As with binary template matching, loose-gray-scale template matching would typically be performed using groups of templates where each template or subgroup of templates is associated with a particular output or action.
In addition to extending binary template matching applications to gray-scale, the loose-gray-scale template matching method introduces an additional tool that can well address other significant image process problems such as enabling a pass through mode for scanned halftones, feature recognition, and segmentation. As with other windowed operators, loose-gray-scale template matching can be performed adaptively and in several dimensions (e.g., 2-dimensional spatial images, 3-dimensional topological images, multiple color planes, frames in a time sequence).
With respect to a preferred statistically optimized design procedure, an observed image and the ideal image may be received in the form of digital images. In accordance with conventional methods for designing a filter and the templates with the filter, the design method tries to map as accurately as possible the observed image to an image that accurately corresponds to the ideal image given certain constraints such as limited number of templates.
With reference to FIG. 1, the relationship of an observed image, an ideal image, matching templates and a generated image is shown. The observed image and the ideal image represent a typical xe2x80x9cbeforexe2x80x9d and xe2x80x9cideal afterxe2x80x9d set of images, respectively. In other words, the observed image and the ideal image can be utilized as training images for a filter design procedure. The observed image and the ideal image may be actual images that are selected based on expert knowledge, or they may contain particular structures that are useful to training. For instance, they may contain precise patterns of particular concern to a specific image processing task.
To further explain, in the filtering operation, given an observed image, in some cases it is possible to generate an image that is identical to the ideal image. Typically, the generated image will not be an exact replica of the ideal image because the filter operation would require knowledge that may not be present. In addition, exact generation of the ideal image would most likely involve exact matching of patterns in the gray-scale image. Such matching is impractical due to the large number of templates and processing time that would be required for most applications. This situation is the result of time constraints, memory constraints, and other system and resource constraints. Further it is recognized that the human visual system has certain limitations in what it can perceive. The excessive computation and storage required for exact pattern matching in gray-scale may yield results that are beyond the perceptive capabilities of the human visual system, or in general, beyond the limitations of the system that will receive the image. Given the above practical system constraints and limitations, a filtering approach using loose-gray-scale template matching has been proposed. In a practical setting with realistic limitations the loose-gray-scale template matching process allows a certain number of templates to have a better match with an observed image to form a generated image closer to the ideal image, than would an attempt to utilize the same number of exact matching templates on the same gray-scale image. If practical limitations with realistic limitations do not allow for many templates, the results of exact matching on gray-scale images would generally be very poor. This new process minimizes costs and generating time of the ideal image, and allows the observer to focus on details that the human visual perception and subsequent image processing modules will actually detect. In addition, the burden of designing an impractical number of exact match templates is mitigated by designing a much smaller set of loose fitting templates.
The present invention separately provides the methods that may be used in conjunction with known methods for line width modification, resolution conversion, resolution enhancement, image restoration and the like.
The present invention separately provides systems and methods that may be used in conjunction with filter design and implementation techniques to optimally yield images processed to better visual quality.
In accordance with one embodiment of the system and methods of the present invention there is provided a template fitting method for fitting a plurality of templates in correspondence with a gray-scale image, comprising: receiving gray-scale image information of an observed image; defining a window of said gray-scale image information so as to enable a loose-gray-scale fit between said defined window and said plurality of templates; extracting a plurality of pixels of said image information using said window to which to fit at least one of the plurality of templates; and fitting one of the plurality of templates to said defined window within a threshold looseness interval associated with the template wherein a looseness interval between the window of image data and the template is less than the threshold looseness interval.
In accordance with another embodiment of the system and methods of the present invention there is provided a multiple template fitting method including a plurality of single templates or plurality of families of templates for correspondence with a gray-scale image, including receiving image information of an observed image; defining a window of the image information so as to enable a loose gray-scale fit between the defined window and the plurality of singular or families of templates; and fitting one of the plurality of singular or families of templates to the defined window within a threshold looseness interval and outputting an item of data indicating a result of a correspondence between a single or family of templates and the received image information within a threshold looseness interval.
In accordance with another embodiment of the system and methods of the present invention there is provided a loose-gray-scale template matching method including at least an initial point for locating within the received image a plurality of pixel points surrounding said initial point, the method including the steps of: locating said initial point and said plurality of pixel points, generating a looseness interval about said located initial point with template information associated therewith, determining which one of a plurality of templates for fitting fits within a threshold looseness interval and, outputting an item of data indicative of whether a template is within the looseness threshold thereby indicating that the template is in agreement therewith.
Loose fit generates a template match identifier that may be used in subsequent processing modules, such as a module that would determine an enhanced output signal.
Accordingly, in some embodiments the system and methods of embodiments of this invention provide a method to decrease the cost of printer electronic hardware to practical levels for example by designing a filter possessing a relatively small number of gray-scale templates.